Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Solution:

  1. public class Solution {
  2.   public List<Integer> majorityElement(int[] a) {
  3.     // we can only have maximum 2 majority elements
  4.     int n = a.length;
  5.     int c1 = 0, c2 = 0;
  6.     Integer m1 = null, m2 = null;
  8.     // step 1. find out those 2 majority elements
  9.     // using Moore majority voting algorithm
  10.     for (int i = 0; i < n; i++) {
  11.       if (m1 != null && a[i] == m1) {
  12.         c1++;
  13.       } else if (m2 != null && a[i] == m2) {
  14.         c2++;
  15.       } else if (c1 == 0) {
  16.         m1 = a[i]; c1 = 1;
  17.       } else if (c2 == 0) {
  18.         m2 = a[i]; c2 = 1;
  19.       } else {
  20.         c1--; c2--;
  21.       }
  22.     }
  24.     // step 2. double check
  25.     c1 = 0; c2 = 0;
  27.     for (int i = 0; i < n; i++) {
  28.       if (m1 != null && a[i] == m1) c1++;
  29.       if (m2 != null && a[i] == m2) c2++;
  30.     }
  32.     List<Integer> res = new ArrayList<Integer>();
  34.     if (c1 > n / 3) res.add(m1);
  35.     if (c2 > n / 3) res.add(m2);
  37.     return res;
  38.   }
  39. }